A message queuing system implements asynchronous communications which enable applications in a distributed processing network to send messages to, and receive messages from, other applications. A message may contain data in any format that is understood by both the sending and receiving applications. When the receiving application receives a request message, it processes the request according to the content of the message and, if required, sends a response message back to the original sending application. The sending and receiving applications may be on the same machine or on separate machines connected by a network. While in transit between the sending and receiving applications, the message queuing system keeps messages in holding areas called message queues. The message queues protect messages from being lost in transit and provide a place for an application to look for messages sent to it when it is ready.
In a proposed message queuing system, a replicated database is maintained for providing directory service for message queuing and routing operations. This directory service database includes a plurality of local databases maintained by respective directory servers on different machines. Each directory server maintains not only data items created by itself but also a replica of data items created by all other servers in the directory service database. When a server creates, modifies, or deletes its data items, it sends replication message packets to the other servers so that they can update their respective replicas. In the context of data replication, a server sending replication information is referred to as a "master," and a server receiving the replication information is referred to as a "slave." If a slave server learns or suspects that it has not received all of the replication information from a master server, it sends a synchronization request to the master server to obtain the missing replication information. To support the synchronization operation, when a server deletes a data item from its local database, it sets up a tombstone to memorialize the deletion so that the deletion can be replicated by other servers. As the configuration of the message queuing system changes over time, data items representing message queuing objects, such as message queues, are constantly created and deleted. With more and more data items deleted from the directory service, the number of tombstones increases correspondingly. Without an effective way to purge the tombstones, the tombstones may grow in an unbounded way and ultimately may fill up the memory space of the directory service database. On the other hand, if the tombstones are purged prematurely, i.e., before other servers have learned about the deletion, the synchronization operation cannot be performed properly.